#include "priority_queue.h"
#include "thread_pool.h"

// there are two types of index:
// 1. index in the heap (starting from 1)
// 2. index in the array (starting from 0)
// always pass/ return the index in the array to the function
// but process it as the index in the heap
// heap_size is the number of element in the heap
// heap_size point to the poisition after the last element

int parent(int index) {
    index++;
    index = index >> 1;
    return index - 1;
}

int left(int index) {
    index++;
    index = index << 1;
    return index - 1;
}

int right(int index) {
    index++;
    index = (index << 1) + 1;
    return index - 1;
}

void swap(pool_task_t* a, pool_task_t* b) {
    pool_task_t temp;

    temp.function = a->function;
    temp.argument = a->argment;
    temp.priority = a->priority;

    a->function = b->function;
    a->argument = b->argument;
    a->priority = b->priority;

    b->function = temp.function;
    b->argument = temp.argument;
    b->priority = temp.priority;
}

void equal(pool_task_t* a, pool_task_t* b) {
    a->function = b->function;
    a->argument = b->argument;
    a->priority = b->priority;
}

int minHeapify(task_queue_t *queue, int index) {
    int leftIndex = left(index);
    int rightIndex = right(index);
    int smallest;

    if (leftIndex < queue->heap_size && (queue->queue)[leftIndex].priority < (queue->queue)[index].priority)
        smallest = leftIndex;
    else
        smallest = index;

    if (rightIndex < queue->heap_size && (queue->queue)[rightIndex].priority < (queue->queue)[smallest].priority)
        smallest = rightIndex;

    if (smallest != index) {
        swap(&((queue->queue)[index]), &((queue->queue)[smallest]));
        minHeapify(queue, smallest);
    }
}

pool_task_t heapExtractMin(task_queue_t *queue) {
    pool_task_t max;

    equal(&max, (queue->queue)[0]);
    equal((queue->queue)[0], (queue->queue)[queue->heap_size - 1]);
    queue->heap_size--;

    minHeapify(queue, 0);

    return max;
}

void heapDecreaseKey(task_queue_t *queue, int index, int key) {
    (queue->queue)[index].priority = key;

    while (index > 0 && (queue->queue)[parent(index)].priority > (queue->queue)[index].priority) {
        swap(&((queue->queue)[parent(index)]), &((queue->queue)[index]));
        index = parent(index);
    }
}

void minHeapInsert(task_queue_t *queue, void (*function)(void *), void *argument, int priority) {
    queue->heap_size = queue->heap_size + 1;

    (queue->queue)[queue->heap_size - 1].function = function;
    (queue->queue)[queue->heap_size - 1].argument = argument;
    (queue->queue)[queue->heap_size - 1].priority = 999;

    heapDecreaseKey(queue, queue->heap_size - 1, priority);
}
